Como já foi dito, há muitos problemas de computação com aplicações práticas importantes para os quais não conhecemos algoritmos eficientes. Isto posto, uma ideia é investigar a complexidade relativa dos problemas em . Um problema não é mais difícil que um problema se uma solução para implica numa solução para com perda de desempenho polinomial relativa a eficiência da solução de . Façamos isso mais preciso.
Se e são problemas computacionais de decisão então uma redução em tempo polinomial de para é um algoritmo eficiente que computa uma função tal que para todo instância de a instância do problema têm a mesma resposta.
Escrevemos .
Notemos que se há uma redução de para e é um algoritmo que resolve então o seguinte algoritmo resolve
Devolva .
ademais, se é um algoritmo de tempo e é um algoritmo de tempo então acima tem consumo de tempo , que é um polinômio sempre que for um polinômio. Notemos que , ou seja, a saída de tem tamanho polinomial no tamanho de . Com isso temos
Teorema 5 Se e então .
Teorema 6 .
Demonstração: Seja uma instância de . Considere o algoritmo que com entrada constrói o grafo completo sobre , constrói a função peso dada por
e toma .
Se é dado pela matriz de adjacências, é uma matriz obtida da matriz de trocando por . O grafo também e dado por uma matriz da mesma ordem. Assim, a descrição é obtida em tempo linear de .
Ainda, se tem um circuito hamiltoniano então tem um circuito hamiltoniano de peso . Se não tem um circuito hamiltoniano então todo circuito hamiltoniano de tem peso .
Um clique num grafo é um subconjunto de vértices que induz um subgrafo completo, isto é, todos os pares de vértices desse subconjunto são arestas no grafo. é o problema: dado um grafo e um inteiro decidir se tem um clique com pelo menos vértices.
Uma cobertura num grafo é um subconjunto de vértices de tal que qualquer aresta de tem pelo menos um vértice em . é o problema: dado um grafo é um inteiro decidir se tem uma cobertura com no máximo vértices.
Teorema 7 .
Demonstração: Dada uma instância de o algoritmo constrói em tempo linear e toma para a instância de . . Seja um clique com vértices em . Então para toda aresta em temos que como é independente em no máximo um dentre e está em de modo que é uma cobertura em com vértices.
Por outro lado, se é uma cobertura com no máximo vértices em , então é independente em , portanto, um clique com vértices em
Uma fórmula booleana satisfazível está em se todas as suas cláusulas têm exatamente 3 literais.
Teorema 8 .
Demonstração: Seja uma instância de . Vamos descrever a construção de uma instância de .
Seja uma cláusula de . A construção de considera 4 casos de acordo com o número de literais da cláusula: , e
Se , digamos que , então criamos a variáveis e escrevemos
Dessa forma, qualquer atribuição que faça verdadeira, faz verdadeira e qualquer extensão de uma atribuição que faça faz verdadeira.
Se , digamos que , então criamos a variáveis e escrevemos
Dessa forma, qualquer atribuição que faça verdadeira, faz verdadeira e qualquer extensão de uma atribuição que faça faz verdadeira.
Se então e .
Finalmente, se , digamos que , então criamos as variáveis e fazemos da seguinte forma
e fica como exercício verificar que se é satisfazível se, e só se, é satisfazível. Com isso, a fórmula é dada pelas variáveis e pelas cláusualas .
Resta mostrar que essa construção pode ser feita em tempo polinomial no tamanho da descrição de .
é a linguagem definida pelo problema de decisão: Dado um grafo e um natural decidir se contém um clique com vértices.
Teorema 9 .
Demonstração: Seja uma instância de e vamos construir uma instância de .
Se tem cláusulas então tem vértices denotados , para e . O vértice corresponde ao literal da cláusula , denotado . As arestas são dadas pelos pares de vértices
com (correspondem a cláusulas diferentes) e cujos literais podem ser simultaneamente verdadeiros (não contraditórios). Notemos que corresponde a um conjunto independente em .
Seja uma atribuição que satisfaz todas as cláusulas de e sejam um literal com valor de cada cláusula. Então é um clique com -vértices em .
Agora, suponha que tem um clique com pelo menos vértices. Seja um subconjunto de vértices de cardinalidade que define um clique em . Como vértices da mesma cláusula não são adjacentes, devemos ter um vértice correspondente a cada cláusula de . Definimos a seguinte atribuição na variáveis de : se é uma variável que corresponde a um vértice de então é verdadeiro, caso contrário, é falso. Assim satisfaz todas as cláusulas.
Resta mostrar que essa construção pode ser feita em tempo polinomial no tamanho da descrição de . Basta notar que tem vértices portanto construímos uma matriz de tamanho que é polinomial no tamanho da representação de .
Exercício 5 é o problema: Dado um grafo e um natural decidir se contém um conjunto independente com vértices. Prove que .
— NP-completude —
Um problema é -difícil se todos os problemas em não são mais difíceis do que no seguinte sentido:
Suponhamos que tenha um algoritmo que o resolve em tempo e seja a redução de para que consome tempo para algum natural . Então, se é uma instância de tamanho para , é uma instância de tamanho para cuja resposta é computada em tempo . Portanto,
Teorema 11 Se algum problema -difícil tem algoritmo eficiente, todos os problemas em têm algoritmo eficiente, isto é, .
Um problema é -completo se
- ,
- é -difícil.
Como consequência dessa definição e da proposição acima
Corolário 12 Se algum problema -completo tem algoritmo eficiente então .
Proposição 13 Se algum problema -completo não tem algoritmo eficiente então nenhum outro problema -completo tem, isto é .
Demonstração: Exercício.
Proposição 14 Se é -completo e então é -difícil.
Demonstração: Exercício.
Teorema 15 (Cook e Levin, 1970) é -completo.
Corolário 16 é -completo.
Demonstração: Vimos que , portanto, é -difícil. Claramente, está em (por quê?).
Corolário 17 é -completo.
Demonstração: Vimos que , portanto, é -difícil. Fica como exercício para o leitor verificar que está em .
Corolário 18 é -completo.
Demonstração: Vimos que , portanto, é -difícil. Fica como exercício para o leitor verificar que está em .
Além desses, dos outros problemas citados nestas notas, é sabido que é -completo e que é -completo. Uma curiosidade: em maio de 2004, o problema caixeiro-viajante nas 24.978 cidades da Suécia foi resolvido (veja aqui).
Há muitos problemas -completos. São tantos e tão pesquisados que muitos pesquisadores acreditam que simplesmente porque se houvesse um algoritmo eficiente para algum desses problemas ele certamente já teria sido descoberto. Veja aqui uma lista de problemas -completos.